package com.atwulidun.dynamicprogramming03.coinchange;

// 问题描述：
// 给定不同面额的硬币 coins 和一个总金额
// amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
// 示例:
// 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1
// 问题分析：
// 类比背包问题，这里要注意的是能否凑成给定的金额，因此在初始化第一行的时候某个金额若不能整除第一种硬币的金额，那么就要标记为-1
public class CoinChange {
    // 存储硬币面额的数组
    private static int[] c = {2, 3, 5};
    // 总金额
    private static int amount = 27;
    // 行表示不同面额的硬币，列表示金额，值表示所需最少的硬币个数
    private static int[][] dp = new int[c.length][amount + 1];
    // 记录状态
    private static int[][] status = new int[c.length][amount + 1];

    public static void main(String[] args) {
        // 初始化
        // 初始化第一列
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        // 初始化第一行
        for (int i = 1; i < dp[0].length; i++) {
            if (i % c[0] == 0) {
                dp[0][i] = i / c[0];
                // 此时也要在status中进行记录
                status[0][i] = i / c[0];
            } else {
                dp[0][i] = -1;
            }
        }

        // 状态转移方程：dp[i][j] = min{dp[i-1][j-k*c[i]+k}
        // 进行空间优化，需要逆序遍历
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                // 记录所需前i种硬币个数的最小值
                int minK = (int) Double.POSITIVE_INFINITY;
                // 记录能使得前i种硬币个数有最小值时当前面额硬币的个数
                int curK = 0;
                for (int k = 0; k <= j / c[i]; k++) {
                    if (dp[i - 1][j - k * c[i]] != -1) {
                        if (dp[i - 1][j - k * c[i]] + k < minK) {
                            minK = dp[i - 1][j - k * c[i]] + k;
                            curK = k;
                        }
                    }
                }
                if (minK == (int) Double.POSITIVE_INFINITY) {
                    dp[i][j] = -1;
                } else {
                    dp[i][j] = minK;
                    status[i][j] = curK;
                }
            }
        }

        // 从后往前遍历
        int i = status.length - 1;
        int j = status[0].length - 1;
        // 特别注意：这里是i>=0
        while (i >= 0 && j > 0) {
            if (status[i][j] != 0) {
                int k = status[i][j];
                while (k > 0) {
                    System.out.println("面额为" + c[i] + "的硬币");
                    j -= c[i];
                    k--;
                }
            }
            i--;
        }

        for (int[] ints : dp) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
        System.out.println("======================");
        for (int[] ints : status) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }

    }
}
